//==============================================================================
// Copyright (c) 2008-2013 Niall Ryan. All Rights Reserved.
//==============================================================================

#ifndef HYDRA_LOCKS_BAKERYLOCK_H
#define HYDRA_LOCKS_BAKERYLOCK_H 1

#include "hydra/backoff/Backoff.h"

namespace Hydra
{
	/**
	 * Implementation of Lamport's Bakery Algorithm. Note that labels are unbounded and fairness will fail when they wrap around.
	 */
	template<unsigned int N>
	class BakeryLock
	{
	public:
		BakeryLock()
		{
			for( unsigned int i=0; i<N; ++i )
			{
				m_flag[i] = false;
				m_label[i] = 0;
			}
		}

		void lock(unsigned int id)
		{
			assert(id < N);
			m_flag[id] = true;

			unsigned int maxLabel = 0;
			for( unsigned int i=0; i<N; ++i )
			{
				unsigned int label = m_label[i];
				if( label > maxLabel )
					maxLabel = label;
			}
			unsigned int newLabel = maxLabel + 1;
			m_label[id].store<FullFence>(newLabel);		//full fence to ensure ordering with subsequent loads, normal acquire/release doesn't handle this

			//loop until there are no other threads before us
			unsigned int numClear = 0;
			unsigned int testId = 0;
			Backoff backoff;
			while( numClear < N )
			{
				if( m_flag[testId] && isLessThan(m_label[testId], testId, newLabel, id) )
				{
					numClear = 0;
					backoff.wait();
				}
				else
					++numClear;

				++testId;
				if( testId >= N )
					testId = 0;
			}
		}

		void unlock(unsigned int id)
		{
			assert(id < N);
			m_flag[id] = false;
		}

	private:
		bool isLessThan(unsigned int labelA, unsigned int idA, unsigned int labelB, unsigned int idB)
		{
			return ((labelA < labelB) || ((labelA == labelB) && (idA < idB)));
		}

		Atomic<bool> m_flag[N];
		Atomic<unsigned int> m_label[N];
	};
}

#endif
